The invention relates to the field of data networks, and in particular to peer to peer overlay networks. Peer to peer networks are distributed data networks without any centralized hierarchy or organization. Peer to peer data networks provide a robust and flexible means of communicating information between large numbers of computers or other information devices, referred to in general as nodes.
An overlay network is a logical or virtual network organization that is imposed on nodes connected by one or more types of underlying physical network connections. In an overlay network, nodes are connected by virtual or logical links, each of which can correspond with one or more paths in an underlying physical network. Overlay networks are typically implemented in hardware and/or software operating in the application layer or other top-level layer of an OSI network stack or other type of networking protocol.
One class of peer to peer overlay networks is referred to as distributed hash table networks. Distributed hash table overlay networks use a hash function to generate and assign one or more key values to a unique node. The set of all possible key values is referred to as a hash space. Nodes are organized in the hash space according to their assigned key values. The hash function is selected so that nodes are approximately evenly distributed throughout the hash space. Distributed hash table overlay networks are typically highly scalable, often supporting millions of nodes; robust, allowing nodes to join or leave frequently; and efficient, routing a message to a single destination node quickly.
There are numerous different types of distributed hash table overlay networks. One type of peer to peer overlay network is a chord network. The chord overlay network protocol is described in detail in “Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”, Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003.
Distributed hash table networks such as Chord can include a feature to route messages between nodes based on a message ID. Typically, nodes subscribe to a message ID. Once a node has subscribed to a given message, that node can receive any messages addressed to that message id. Additionally, a node can send messages to the message ID. Messages sent to a message ID will be distributed to any other nodes subscribed to that same message ID.
This message routing feature in prior distributed hash table networks distributes messages between nodes without requiring nodes to know the location of the other nodes. In typical implementations, an intermediate node is assigned responsibility for routing messages to all of the nodes subscribing to a message ID. In prior implementations, the intermediate node receives all messages associated with a message ID and resends these messages as they are received to all nodes currently subscribed to the message ID.
This message routing in prior distributed hash table networks is inflexible and does not provide for any caching, processing, or other manipulation of messages in transit between nodes. This limits the potential applications of message routing in distributed hash table networks.
Additionally, this type of message routing does not handle changes in the network gracefully. For example, if additional nodes subscribe to a message ID after other nodes have already exchanged messages, the distributed hash table network cannot automatically synchronize the newly subscribed nodes with data from previously routed messages.
It is therefore desirable for a system and method to provide message routing that enables additional applications and improves the performance of distributed hash table networks. It is also desirable for a system and method to allow applications to specify message routing behavior based on a variety of criteria. It is further desirable for the system and method to allow applications to specify caching, processing, and other manipulations of messages in transit between nodes. It is additionally desirable for the system and method to synchronize nodes with message data automatically according to application requirements upon subscribing to a message ID.